package leetcode
/*
 * @lc app=leetcode.cn id=1081 lang=golang
 *
 * [1081] 不同字符的最小子序列
 */

// @lc code=start
func smallestSubsequence(s string) string {
	left := [26]int{}
	for _, ch := range s {
		left[ch-'a']++
	}
	stack := make([]rune, 0, 26)
	inStack := [26]bool{}
	for _, ch := range s {
		if !inStack[ch-'a'] {
			for len(stack) > 0 &&
				stack[len(stack)-1] > ch &&
				left[stack[len(stack)-1]-'a'] > 0 {
				inStack[stack[len(stack)-1]-'a'] = false
				stack = stack[:len(stack)-1]
			}
			stack = append(stack, ch)
			inStack[ch-'a'] = true
		}
		left[ch-'a']--
	}
	return string(stack)
}
// @lc code=end

